package leetcode_day._2021._202109._1120;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/15 8:46
 * 寻找峰值
 * 算法：二分查找  数组
 * 由于题目中的元素没有相等的情况，所以只要找到最大值即可
 * -------------------------------------------------
 * 二分查找一直往高处走，则一定有峰值，因为 nums[-1] = nums[n] = -∞
 * 所以最后一定会有峰值
 * 使用二分查找找到最大值
 */
public class _15_162 {
    public static void main(String[] args) {
        System.out.println(new _15_162().findPeakElement(new int[]{1, 2, 3, 1}));
    }

    public int findPeakElement(int[] nums) {
        int ans = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > nums[ans]) ans = i;
        }
        return ans;
    }

    public int findPeakElement_dichotomy(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1]) l = mid + 1;
            else r = mid;
        }
        return l;
    }

    public int findPeakElement2(int[] nums) {
        // 因为最后一个元素肯定是峰顶或者峰顶的右边, 不用进行二分
        int l = 0, r = nums.length - 2;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[mid + 1]) l = mid + 1;
            else r = mid - 1;
        }
        return l;
    }


}
